Conventionally, a navigation terminal detects its current location, that is, an origin of a trip through a Global Positioning System (GPS) connection, receives information about a destination of the trip from a user, and internally calculates a route based on the origin and the destination. Along with the recent proliferation and increased performance of smartphones, services have become popular, in which a traffic and route information providing server provides route information, real-time traffic information related to routes, and other various information to Personal Navigation Devices (PNDs) over a mobile communication network.
Particularly in the situation where various navigation services are available, the Open Mobile Alliance (OMA) standardization organization is working on standardization of Dynamic Navigation Enabler (DynNav) that provides real-time traffic information by Peer to Peer (P2P) communication through an Internet Protocol (IP)-based network of a mobile communication network or a wireless network, rather than Traffic Protocol Expert Group (TPEG) information is transmitted over a Digital Multimedia Broadcasting (DMB) network that provides information in a broadcast signal. The standard considers a navigation terminal and a service type largely in two ways for a smartphone.
First, a traffic and route information providing server performs complex route computation, instead of a navigation application loaded in a smartphone, and indicates a calculated route to the smartphone. Second, owing to the improved performance of a smartphone, an application loaded in the smartphone performs or a navigation terminal equipped with a mobile communication modem performs route computation. In this case, the traffic and route information providing server does not provide route information. Rather, once the terminal registers a calculated route to the server, the terminal can receive from the server only real-time traffic information related to the registered route in a customized manner by IP-based P2P communication, not in a conventional broadcast signal.
FIG. 1 illustrates Navigation Device (ND) types. NDs may be classified into a type 110 that additionally provides TPEG-based traffic information transmitted through a broadcasting network such as a DMB network, a type 120 that additionally provides traffic information in an IP-based manner, for example, over a mobile communication network or a Wireless Fidelity (Wi-Fi) network, and a standalone type 130 that tracks the location of a vehicle through a GPS connection without connecting to other communication media, generates route information, and provides the route information.
DynNav under standardization in the OMA LOC WG belongs to the type 120 that provides IP-based traffic information, specifically by P2P communication. The following two types of NDs are defined in DynNay.
1. Smart ND: a device that can calculate a route on its own and thus requests only real-time traffic information to a DynNav server without receiving route information from the DynNav server.
2. Lightweight ND: a device that cannot calculate a route on its own and thus requests all real-time traffic information including route information to a DynNav server.
Since traffic information is requested and provided in a RESTful-based manner in a conventional DynNav system, the following route information formats are used and each information format can be defined by XML Schema Definition (XSD).
1) Trip Structure: a terminal initially acquires basic information such as an origin and a destination from a user, for route setting, and provides the acquired information to a server. The trip structure includes subsets corresponding to a plurality of route structures.
TABLE 1ElementTypeOptionalDescriptionoriginWGS84Location_PointChoiceLocation_Point structure is defined in tpeg-locML [TTI LOC]. At least one elementoriginWGS84 or originAddress MUST bespecified when Trip resource is created. Thiselement is mandatory when the Trip resourceis read by the client.This field can be used to indicate the assumedcurrent position of the client, enabling routeinformation updating procedure on the server.originAddressCivic LocationChoiceCivic Location Format is defined by IETFFormat[RFC 5139]. At least one elementoriginWGS84 or originAddress MUST bespecified.destinationWGS84Location_PointChoiceLocation Point structure is defined in tpeg-locML [TTI LOC]. At least one elementdestinationWGS84 or destinationAddress ordestionation3rdParty MUST be specified whenTrip resource is created. This structure ismandatory when the Trip resource is read byhe client.destinationAddressCivic AddressChoiceCivic Location Format is defined by IETF[RFC 5139]. At least one elementdestinationWGS84 or destinationAddress ordestination3rdParty MUST be specified whenTrip resource is created. This structure may beprovided by the server in case the user definesa destination using destinationWGS84 ordestionation3rdParty structures.destination3rdPartyxsd:stringChoiceOne element among destinationWGS84,destinationAddress, or destionation3rdParty MUSTbe specified when Trip resource is created.thirdPartyIDTypeThirdPartyIDType-YesInditae which type of the thirdparty ID is usedListin origin3rdParty or destination3rdParty.If destination3rdParty exists,thirdPartyIDType shoud exist.waypointsLocation_PointYesLocation_Point structure is defined in tpeg-[0 . . . unbounded]locMLstartingTimexsd:dateTimeYesStarting time of the planned trip. If notpresent, current time is assumed.tollRoadxsd:booleanYesIf true or not present, toll road are allowed.)vehicleTypeVehicle_InfoYesVehicle_Info structure is defined in tpeg-rtmMLcalculateRoutexsd:booleanYesIf false or not present, server should notpropose routes.requestedEventsCategoriesxsd:stringyesCategories of traffic information, related to the[0 . . . unbounded]defined Trip, requested by the application.This field shall be encoded according to thelist of values defined in the rtm00 tableavailable in TTI RTM.If this field is not present, the server MUSTprovide traffic information for all definedcategories (including network performanceparameters).linkcommon:LinkYesLinks to routes related to the trip. Attribute[0 . . . unbounded]“rel” must be set to “Route”.resourceURLxsd:anyURIYesSelf-referring URL. SHALL NOT be includedin POST requests, MUST be included inresponses to any HTTP method that returns anentity body, and in PUT requests.)
2) Route Structure: a route structure is expressed as a plurality of segments as a way to represent total routes calculated using the trip structure.
TABLE 2ElementTypeOptionalDescriptiontravellingTimexsd:floatYesTotal travelling time (in minutes) for the routedistancexsd:floatYesTotal distance (in Km) of the routeoriginLocation_PointNoLocation_Point structure is defined in tpeg-locML [TTI LOC].partialRouteInformationxsd:booleanYesIf set to true, the Route is described with partialinformation: only changed segments sequenceis provided with respect to a reference route.The reference route is defined in link field ofthis structure.The partial encoding schema MAY be used forfull routes resources.If this field is absent or set to false, the routeinformation is complete.firstSegmentxsd:integerYesThis field represents one or more index of the[0 . . . unbounded]first segment in the reference route segmentssequence to be replaced by partial routesegments sequence. In a partial route, asequence of deviations MAY be provided withrespect to the reference route: for eachdeviation it is provided the index of the firstsegment in the reference route that has to bereplaced by partial route segments sequence.This field is present only in case of partial routeencoding schema (partialRouteInformation setto True)lastSegmentxsd:integerYesThis field represents one or more index of the[0 . . . unbounded]last segment in the reference route segmentssequence to be replaced by the segmentssequence of partial route. Only used for thepartial route case.In a partial route, a sequence of deviationsMAY be provided with respect to the referenceroute: for each deviation it is provided the indexof the last segment in the reference route thathas to be replaced by partial route segmentssequence.This field is present only in case of partial routeencoding schema (partialRouteInformation setto True).numSegmentsxsd:integerYesThis field represents the number of segments[0 . . . unbounded]that constitutes each single deviation of thepartial route. Only used for the partial routeinformation case.In a partial route, a sequence of deviationsMAY be provided with respect to the referenceroute: for each single deviation the number ofdescribing segments is provided. The sum ofthe number of segment of each deviation shouldbe equal to the number of segments provided inthe partial route.This field is present only in case of partial routeencoding schema (partialRouteInformation setto True).trafficEventsCategorizedEvent-YesList of traffic events as defined in tpeg-rtmMLListReference[TTI RTM], grouped into categories.[0 . . . unbounded]linkcommon:LinkYesLink to reference route resource. Two[0 . . . 2]reference route resources are present.1) (Reference to the route for which it isproposed as alternative. Attribute “rel” mustbe set to “Route”.)2) Reference to the route for which the partialroute information is referred. Attribute “rel”must be set to “ReferenceRoute”.resourceURLxsd:anyURIYesSelf-referring URL. SHALL NOT be includedin POST requests, MUST be included inresponses to any HTTP method that returns anentity body, and in PUT requests.
3) Segment Structure: it is a structure that represents each segment. The segment structure may define a real-time traffic state corresponding to the segment as well as the length of the segment, in TPEG.
TABLE 3ElementTypeOptionalDescriptionoriginPointLocation_PointYesThis field represents the origin of the segmentencoded according to Location_Point structure asdefined in tpeg-locML.In case segment structure is used for describing aroute and this field is not present, the starting pointof the segment should be assumed equal to theending point of the previous segment, or the triporigin in case of the first segment of the route. Incase of partial route, the origin of the first segment ofeach deviation is the ending point of the last validsegment in reference route.endPointLocation_PointNoLocation_Point structure as defined in tpeg-locML[TTI LOC]. The starting point of the segment shouldbe assumed equal to the ending point of the previoussegment (or the trip origin for the first segment))midwayPointLocation_PointYesLocation_Point structure as defined in tpeg-locML[0 . . . unbounded][TTI LOC]polyLinexsd:stringYesPolyline is used to describe the shape of a segment.This field is a string that contains a sequence ofgeographic points expressed in WGS84 coordinates.Each single point is encoded as a sequence ofWGS84 Latitude,Blank (character),WGS84 Longitude,Colon (character),Blank (character).The shape of segments is provided by the server ifexplicitly requested by the application.The level of polyline resolution is defined by theDynNav Server. When used in full route resource,the polyline resolution has to target a correctrepresentation of segments on turn-by-turnnavigation maps. In summarized route resource theresolution has to target the high level representationof the route on top of roads maps.Polyline example:45.12345 7.009876, 45.12355 7.09866, . . .)linkNamexsd:stringYesName of the road that the segment belongs todistancexsd:floatYesLength of the segment in kmregularTravellingTimexsd:floatYesEstimated regular time to drive through the segmentin low traffic conditions, expressed in minutesperformanceParametersPerformanceParametersYesThis field contains performance parameters related[0 . . . unbounded]to each segment.When segment structure is used to report networkperformance parameters for an area, a sequence ofperformanceParameters structure is included in thesegment structure, providing information for therequested time interval and time resolution.positionUpdatexsd:booleanYesIf present and set to True, the application isrequested to upload its current position when theNavigation Device enters this segment.
4) Subscription List Structure
TABLE 4ElementTypeOptionalDescriptionsubscrip-SubscriptionYesIt may contain an arraytion[0 . . .of Subscription.unbounded]re-xsd:anyURIYesSelf referring URL. ThesourceURLresourceURL SHALL NOTbe included in POST requestsby the client, but MUSTbe included in POST requestsrepresenting notifications bythe server to the client,when a complete representationof the resource is embeddedin the notification. TheresourceURL MUST be alsoincluded in responses to anyHTTP method that returns anentity body, and in PUTrequests.
5) Subscription structure
TABLE 5ElementTypeOptionalDescriptioncallbackReferencecommon:CallbackReferenceNoClient's Notification endpoint andparameters.linkcommon:LinkNoReferences to resources subscribed by the[1 . . . unbounded]application. Attribute “rel” indicates the typeof resource subscribed. It may assume thefollowing values:“Trip”: in order to get notified about:new traffic events andperformance parameterrelated to the set of routesdefined for the tripnew alternative routeproposals“Area”: in order to be notified ofnew traffic events and performanceparameters updatesAttribute “href” specifies the URL ofsubscribed resource. Subscribed resource'stype must be the same of that specified in“rel” attribute,Note: notified information for an existingroute are:a) new traffic events provided with linksincluded in the route resource itself;b) performance parameters available inupdated performanceParameter filed ofsegment structures.)trackingProcxsd:booleanYesIf present and set to True, the applicationcommunicate to the server user's availabilityto provide position information through anexternal location application.deviceLocationxsd:anyURIYesThis parameter is used by the server forURIaccessing Navigation Device positioninformation.tracking3rdPartyxsd:booleanYesIf present and set to True, the DynNavserver tracks the 3rd party position andnotifies the availability of updatedinformation when the 3rd party position ischanged.resourceURLxsd:anyURIYesSelf referring URL. The resourceURLSHALL NOT be included in POST requestsby the client, but MUST be included inPOST requests representing notifications bythe server to the client, when a completerepresentation of the resource is embeddedin the notification. The resourceURL MUSTbe also included in responses to any HTTPmethod that returns an entity body, and inPUT requests.
FIG. 2 is a diagram illustrating a signal flow for an operation of a lightweight ND in a conventional DynNav system. Because the lightweight ND does not support route calculation in view of its capability, the lightweight ND should request route information to a server and receive the route information from the server. The lightweight ND has the following main functionality.                The lightweight ND transmits trip information to the server, for use in route calculation at the server.        The lightweight ND receives information about a set of routes (including a recommended route) calculated by the server from the server.        The lightweight ND subscribes to a notification service to receive real-time traffic information from the server.        
A description will now be given with reference to the flow diagram of FIG. 2.
1. A user of an application defines journey parameters and the application transmits the parameters to a server. The server calculates a set of proposed routes based on the received parameters using related traffic information. The server sends a created “trip” resource including the route identifiers of the proposed routes to the application as a response.
2. The application accesses the set of routes of a summarized format. This step is repeated with respect to all the routes proposed by the server. However, when the length and complexity of the trip are restricted or network quality is inappropriate, full format route information may be used in this step. The application may request shape information (a polyline of a WGS84 coordinate system) of the proposed routes unavailable in a navigation device.
3. The user selects one of the set of proposed routes and the application accesses the full format information of the route selected by the user. The application may request shape information (a polyline of a WGS84 coordinate system) of the proposed routes unavailable in a navigation device. When the full format route is acquired in step 2, this step is not required. The server sends the selected route information along with the related traffic information as a response.
4. The application accesses traffic events related to the route using links to provided traffic event resources. Access to the traffic events may be restricted to categories selected by the user.
5. The application removes unnecessary routes which were previously proposed by the server but were not selected by the user.
6. The application requests the server to create subscription to a notification service for the trip (route(s)). The server notifies the application of the following events.
a. update of performance parameters of all routes related to the trip and new traffic events (for the selected categories)
b. proposal of alternative routes due to traffic problems of routes to be used
c. route to an updated destination and/or a third party when the destination of the trip is the position of the third party and the position of the third party is changed. For notification of this information, the application should request a procedure of tracking the position of the third party from the server upon subscription to the notification service.
7. When a vehicle (including the application) escapes from the used route and makes a detour, the application modifies an origin parameter of the trip resource. The server recognizes that the current position of the vehicle is not on the used route and calculates a new route using a new origin. The server sends an identifier of the new route as a response and removes the previous route (and the identifier thereof). When the modified origin parameter corresponds to the previous route, the server uses this information in order to delete an already passed segment from the route.                Step 7 is performed when the vehicle makes a detour or escapes from the route, when the vehicle moves from a previously reported point by a specific distance and/or when the vehicle enters a segment in which the server requests upload of the current position of the vehicle.        
8. The server delivers the notification resource to the application using links to the modified resources including the trip and the route including the updated traffic information (traffic events and performance parameters).
8. The application accesses the newly proposed route along with the performance parameters and the traffic events. Since the application subscribes to the notification service for the trip resource, the subscription includes the newly proposed route.
9. When the server detects the traffic events on the proposed routes, severe traffic congestion and/or change of the position of the third party, the server sends notification using a uniform resource locator (URL) of the updated information.
10. The application accesses the update information of the used route, new traffic events and the proposed alternative routes. Since the subscription to the notification service includes all routes related to the trip, the notification extends to the proposed alternative route. When the position of the third party is changed, the application accesses the changed position of the third party and/or the updated route resource as a destination.
In the meantime, during the lightweight ND service, it is often necessary for the user to request a path (or route) including one or more waypoints. For example, in order to provide more various services regarding a navigation service as well as to improve user satisfaction or user experience, a method for requesting a path (or route) including one or more waypoints and providing the requested path through the server is needed. For example, the user must visit various geographical locations within a predetermined time, such that the user can input various waypoints when requesting the path.
In addition, the above-mentioned method for requesting or providing a path (or route) including one or more waypoints must consider some important matters because the path (or route) includes one or more waypoints. The present invention proposes a method for providing a path (or route) including at least one waypoint and a solution for addressing some issues associated with the method.